# 第K个缺失的正整数: https://leetcode-cn.com/problems/kth-missing-positive-number/

class Solution:
    def findKthPositive(self, arr: list, k: int) -> int:
        """
            直接模拟过程
        """
        cur = count = 0 = num = 0
        # 当达到次数时，结束循环
        while count < k:
            num += 1
            if cur < len(arr):
                if arr[cur] != num:
                    count += 1
                else:
                    cur += 1
            else:
                count += 1
                
        return num


# 二分查找： 代码都不复杂~ 但是想到这样写却很不容易
class Solution:
    def findKthPositive(self, arr: list, k: int) -> int:
        if arr[0] > k:
            return k
        
        l, r = 0, len(arr)
        while l < r:
            mid = (l + r) >> 1
            x = arr[mid] if mid < len(arr) else 10**9
            if x - mid - 1 >= k:
                r = mid
            else:
                l = mid + 1

        return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1]



arr = [2,3,4,7,11]
k = 5

s = Solution()
rst = s.findKthPositive(arr, k)
print(rst)

